package 剑指Offer.中等;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author caihe
 * @date 2022/9/15 9:21
 */
public class _59II队列的最大值 {

    class MaxQueue {

        Queue<Integer> queue;
        Deque<Integer> deque;

        public MaxQueue() {
            queue = new LinkedList<>();
            deque = new LinkedList<>();
        }

        public int max_value() {
            return deque.isEmpty() ? -1 : deque.peekFirst();
        }

        public void push_back(int value) {
            // 入队
            queue.add(value);
            // 将小于value的元素从deque中移除
            while (!deque.isEmpty() && deque.peekLast() <= value) {
                deque.removeLast();
            }
            deque.addLast(value);
        }

        public int pop_front() {
            if (queue.isEmpty()) {
                return -1;
            }
            // 移除队头时判断是否为最大值 最大值则移除
            if (queue.peek().equals(deque.peekFirst())) {
                deque.removeFirst();
            }
            return queue.poll();
        }
    }

}
